//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
// Related Topics 字符串 动态规划 
// 👍 5262 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * [P5]_最长回文子串
 * @author cjl
 * @date 2022-05-28 10:29:29
 */
public class P5_LongestPalindromicSubstring{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P5_LongestPalindromicSubstring().new Solution();
          System.out.println("args = " + solution.longestPalindrome("sfdsaljlkdlls"));
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
      class Solution {
          public String longestPalindrome(String s) {
              if(s.length() <= 1){
                  return s;
              }
              /**
               * 解题思路：先作一个简单的判断字符串是否是回文的方法，再遍历字符串中每一个可能的字符判断；
               * 核心增加缓存， F[i,j]为回文的充分必要条件是F[i+1,j-1]为回文字符切s[i]==s[j];
               * 可以将算法时间复杂度从O[n^3]降为O[n^2]
               */
              Map<String,Boolean> map = new HashMap();
              String result = s.substring(0,1);
              for(int i= 0; i < s.length(); i++){
                  for(int j = i+1; j < s.length(); j++){
                      String tmpKey = (i+1) + "_" + (j-1);
                      if(null == map.get(tmpKey)){
                          boolean r = isHuiwen(s.substring(i,j+1),i, j+1);
                          map.put(i+"_" + j, r);
                      }else if(map.get(tmpKey) && s.charAt(i) == s.charAt(j)){
                          map.put(i+"_"+ j, true);

                      }else if(!map.get(tmpKey) || s.charAt(i) != s.charAt(j)){
                          map.put(i + "_" + j , false);
                      }
                      if(map.get(i+ "_"+j) && s.substring(i,j+1).length() > result.length()){
                          result = s.substring(i,j+1);
                      }
                  }
              }
              return result;
          }

          private boolean isHuiwen(String s , int left , int right){
              if(left >= right) {
                  return true;
              }
              while (left < right){
                  if(s.charAt(left) == s.charAt(right)){
                      return isHuiwen(s, left+1, right -1 );
                  }else{
                      return false;
                  }
              }
              return true;
          }
      }
//leetcode submit region end(Prohibit modification and deletion)

  }